package org.example.algorithm.binarytree;

import org.example.algorithm.TreeNode;

import java.util.HashMap;
import java.util.Map;

//输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
//输出：[1,2,3,4,5,6,7]
public class ConstructFromPrePostSolution {
    public static void main(String[] args) {
        ConstructFromPrePostSolution solution = new ConstructFromPrePostSolution();
//        int[] preorder = {1,2,4,5,3,6,7};
//        int[] postorder = {4,5,2,6,7,3,1};
        int[] preorder = {1};
        int[] postorder = {1};
        solution.constructFromPrePost(preorder, postorder);
    }

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> posMap = new HashMap<>();
        for (int i=0;i<postorder.length;i++) {
            posMap.put(postorder[i], i);
        }
        return doCreateTree(preorder, postorder, 0, preorder.length-1, 0, postorder.length-1, posMap);
    }

    private TreeNode doCreateTree(int[] preorder, int[] postorder, int preStart, int preEnd
            , int postStart ,int postEnd, Map<Integer, Integer> posMap) {
        if (preStart > preEnd || preStart >= preorder.length) {
            return null;
        }
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int pos = posMap.get(preorder[preStart+1]);
        //左子树是否为空无法判断
        int leftLen = pos-postStart+1;
        root.left = doCreateTree(preorder, postorder, preStart+1, preStart+leftLen, postStart, pos, posMap);
        root.right = doCreateTree(preorder, postorder, preStart+leftLen+1, preEnd, pos+1, postEnd-1, posMap);
        return root;
    }
}
